"""
    create by IAmFiveHigh on 2023/10/3
"""
import math
from typing import List


class Solution:
    @staticmethod
    def search(nums: List[int], target: int) -> int:
        l = 0
        r = len(nums) - 1
        while l <= r:
            mid = l + math.floor((r - l) / 2)
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                l = mid + 1
            elif nums[mid] > target:
                r = mid - 1
        return -1

    @classmethod
    def search_by_recursion(cls, nums: List[int], target: int) -> int:
        return cls._recursion(nums, target, 0, len(nums) - 1)

    @classmethod
    def _recursion(cls, nums: List[int], target: int, left: int, right: int):
        if left > right:
            return -1
        mid = left + math.floor((right - left) / 2)
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            return cls._recursion(nums, target, mid + 1, right)
        elif nums[mid] > target:
            return cls._recursion(nums, target, left, mid - 1)


def test(nums, fun, target):
    result = fun(nums, target)
    if result != -1:
        print(f"{nums}第{result}位 = {target}")
    else:
        print(f"{nums}中没有{target}")


if __name__ == '__main__':
    n = [-1, 0, 3, 5, 9, 12]

    test(n, Solution.search, 9)
    test(n, Solution.search, 10)
    test(n, Solution.search_by_recursion, 9)
    test(n, Solution.search_by_recursion, 10)
